from __future__ import division, print_function
from ways import load_map_from_csv
from pqdict import PQDict
#from test.test_threading_local import target
from cmath import sqrt
from ways import compute_distance
#from ourFunctions import areConnected
import math
 
class Node:
    def __init__(self, junctionNumber, gCost, hCost, parent):
        self.junctionNumber = junctionNumber
        self.gCost = gCost
        self.hCost = hCost
        self.fCost = gCost + hCost
        self.parent = parent
    
    def __cmp__(self, other):
        return cmp(self.fCost, other.fCost)
'''
/* name: makeList
/* Descriprion: creates a simple list of junctions ID's of the best path - from strat node to target node
/* paramIn: target - target node
/* return: a simple list of path
'''
def makeList(target):
    currentState = target
    path = []
    while currentState.parent is not None:
        path.append(currentState.junctionNumber)
        currentState = currentState.parent
    path.append(currentState.junctionNumber)   #adding the start node
    return path[::-1]

'''
/* name: generateHuristicFunc
/* Descriprion: generates a huristic function that estimates the cost of a path between a junction and the problem's target
/* paramIn: target - target junction
/* paramIn: lightsWeight: paratial weight of lights (vs. speed) in the cost function
/* return: a huristic function that receives a junction and returns the estimated cost of a path
         between the junction and the problem's target
'''
#TODO: write the *real* huristic function
def generateHuristicFunc(target, lightWeight):
    def huristicFunc(currentJunction):
        distance = compute_distance(currentJunction.lat, currentJunction.lon, target.lat, target.lon)
        return (1-lightWeight)*(distance/110)*60  #computing time minutes
    return huristicFunc

'''
/* name: generateGFunction
/* Descriprion: generates a function that computes the g cost value between 2 junctions
/* paramIn: roads - the roads graph 
/* paramIn: lightsWeight: paratial weight of lights (vs. speed) in the cost function
/* return: a function that gets a link and a junction and returns the cost of driving the link and getting to the junction
'''
#TODO: the real gFunction is in a comment, just for easy testing
def generateGFunction(roads, lightsWeight):
    
    firstIteration = 1
    for link in roads.iterlinks():
        if firstIteration == 1:
            maxTimePerLink = (link.distance/1000)/roads.link_speed(link)*60
            firstIteration = 0
        if maxTimePerLink < (link.distance/1000)/roads.link_speed(link)*60:
            maxTimePerLink = (link.distance/1000)/roads.link_speed(link)*60
    def gFunction(link, nextJunction):
        return ((1-lightsWeight)*((link.distance/1000)/roads.link_speed(link))*60 + lightsWeight*roads.has_traffic_lights(nextJunction)*maxTimePerLink) 
    return gFunction


'''
/* name: aStarSearchAux
/* Descriprion: computes the best path (fastest and smallest ampunt of lights) between start junction and target junction 
/* paramIn: start - the start junction 
/* paramIn: target - the target junction
/* paramIn: lightsWeight: paratial weight of lights (vs. speed) in the cost function
/* paramIn: roads - roads map
/* return: a tuple with 3 values: (simple list of junctions in the best path, cost of best path, huristic cost of best path)
'''
def aStarSearchAux(start, target, lightsWeight, roads):
    huristicFunc = generateHuristicFunc(roads[target], lightsWeight)
    gFunction = generateGFunction(roads, lightsWeight)
    huristicCost = huristicFunc(roads[start]) #computing the h value of the start junction
    open = PQDict({start: Node(start, 0, huristicCost, None)})  #insert the start junction to the open list
    close = {}  #initiate an empty close list
    while len(open):
        next = open.popitem()       #notice: the next item is a tuple: 1st element is the junction's number, 2nd element is of type Node
        close[next[0]] = next[1]    #insert the poped item (the item with smallest f cost in open list) into close list
        if target == next[0]:       #check if we have finished!
            return [makeList(next[1]),next[1].gCost, close[start].hCost]
        for link in roads[next[0]].links:   #go over all links from the 'next' junction
            newG = next[1].gCost + gFunction(link, roads[link.target])
            huristicCost = huristicFunc(roads[link.target])
            if link.target in open:
                oldJunction = open.get(link.target)
                if newG < oldJunction.gCost:
                    del open[link.target]
                    open[link.target] = Node(link.target, newG, huristicCost, next[1])
            elif link.target in close:
                closedJunction = close[link.target]
                if newG < closedJunction.gCost:
                    del close[link.target]
                    open[link.target] = Node(link.target, newG, huristicCost, next[1])
            else:
                open[link.target] = Node(link.target, newG, huristicCost, next[1])

'''
/* name: aStarSearch
/* Descriprion: computes the best path (fastest and smallest ampunt of lights) between start junction and target junction 
/* paramIn: start - the start junction 
/* paramIn: target - the target junction
/* paramIn: lightsWeight: paratial weight of lights (vs. speed) in the cost function
/* paramIn: roads - roads map
/* return: a simple list of junctions in the best path
'''
def aStarSearch(start, target, lightsWeight, roads = None):
    if not roads:
        roads = load_map_from_csv()
    return aStarSearchAux(start, target, lightsWeight, roads)[0]
                        
if __name__ == '__main__':
    'self test your code' 
    'note: assigning variables here make them global! use functions instead.'
  #  for x in aStarSearch(0,4,0):
        #print (x)
    